//描述   https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=13&tags=&title=&difficulty=0&judgeStatus=0&rp=0
//        大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
//        斐波那契数列是一个满足 fib(x)  x=1,2时，返回1 ; n>x: fib(x) = fib(x-1)+fib(x-2)
//        的数列
//        数据范围：1\leq n\leq 391≤n≤39
//        要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n) ，本题也有时间复杂度 O(logn)O(logn) 的解法
public class Solution11 {
    //1. 递归，用时较长  2^n时间复杂度
    public int Fibonacci(int n) {
        if(n==1||n==2){
            return 1;
        }
        return Fibonacci(n-1)+Fibonacci(n-2);

    }
    // 2.直接算出来 复杂度 n
    public int Fibonacci2(int n) {
        int a=1;
        int b=1;
        int c=1;
        if(n==0){
            return 0;
        }
        if(n<3){
            return 1;
        }
        for(int i=2;i<=n;i++){
            b=c;
            a=c-a;
            c=a+b;
        }
        return c;

    }
}
